package com.gitee.ywj1352.算法.week04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class 二叉树的层序遍历 {

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t5.left = t3;
        t5.right = t8;
        t3.left = t2;
        t3.right = t4;
        t2.left = t1;
        t8.left = t6;
        t8.right = t7;

        List<List<Integer>> lists = levelOrder(t5);

        System.out.println(lists);

    }


    public static List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> nodeDeque = new ArrayDeque<>();
        nodeDeque.addFirst(root);
        List<List<Integer>> lists = new ArrayList<>();
        while(!nodeDeque.isEmpty()){
            int size = nodeDeque.size();
            ArrayList<Integer> integers = new ArrayList<>();
            //关键点 记录本层的 节点数
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = nodeDeque.removeFirst();
                int val = treeNode.val;
                integers.add(val);
                if (treeNode.left != null){
                    nodeDeque.addLast(treeNode.left);
                }
                if (treeNode.right != null){
                    nodeDeque.addLast(treeNode.right);
                }
            }
            lists.add(integers);
        }
        return lists;
    }


}
